﻿//#include <iostream>
//using namespace std;
//const int N = 100010;
//long long arr[N], dp[N];
//int n, q;
//int main()
//{
//	cin >> n >> q;
//	// 读取数据
//	for (int i = 1; i <= n; i++) cin >> arr[i];
//	// 处理前缀和数组
//	for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
//	while (q--)
//	{
//		int l, r;
//		cin >> l >> r;
//		// 计算区间和
//		cout << dp[r] - dp[l - 1] << endl;
//	}
//	return 0;
//}


//#include <iostream>
//using namespace std;
//const int N = 1010;
//int arr[N][N];
//long long dp[N][N];
//int n, m, q;
//int main()
//{
//	cin >> n >> m >> q;
//	// 读⼊数据
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <= m; j++)
//			cin >> arr[i][j];
//	// 处理前缀和矩阵
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <= m; j++)
//			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j -1];
//	// 使⽤前缀和矩阵
//	int x1, y1, x2, y2;
//	while (q--)
//	{
//		cin >> x1 >> y1 >> x2 >> y2;
//		cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 -1] << endl;
//	}
//}



//class Solution {
//public:
//	int pivotIndex(vector<int>& nums) {
//		int n = nums.size();
//		vector<int> lsum(n), rsum(n);
//		// 预处理前缀和后缀和数组
//		for (int i = 1; i < n; i++)
//			lsum[i] = lsum[i - 1] + nums[i - 1];
//		for (int i = n - 2; i >= 0; i--)
//			rsum[i] = rsum[i + 1] + nums[i + 1];
//		// 判断
//		for (int i = 0; i < n; i++)
//			if (lsum[i] == rsum[i])
//				return i;
//		return -1;
//	}
//};


//class Solution
//{
//public:
//	vector<int> productExceptSelf(vector<int>& nums)
//	{
//		int n = nums.size();
//		vector<int> lprod(n + 1), rprod(n + 1);
//		lprod[0] = 1, rprod[n - 1] = 1;
//
//		// 预处理前缀积以及后缀积
//		for (int i = 1; i < n; i++)
//			lprod[i] = lprod[i - 1] * nums[i - 1];
//		for (int i = n - 2; i >= 0; i--)
//			rprod[i] = rprod[i + 1] * nums[i + 1];
//
//		// 处理结果数组
//		vector<int> ret(n);
//		for (int i = 0; i < n; i++)
//			ret[i] = lprod[i] * rprod[i];
//		return ret;
//	}
//};



//class Solution
//{
//public:
//	int subarraySum(vector<int>& nums, int k)
//	{
//		unordered_map<int, int> hash; // 统计前缀和出现的次数
//		hash[0] = 1;
//		int sum = 0, ret = 0;
//		for (auto x : nums)
//		{
//			sum += x; // 计算当前位置的前缀和
//			if (hash.count(sum - k)) ret += hash[sum - k]; // 统计个数
//			hash[sum]++;
//		}
//		return ret;
//	}
//};


class Solution
{
public:
	int subarraysDivByK(vector<int>& nums, int k)
	{
		unordered_map<int, int> hash;
		hash[0 % k] = 1; // 0 这个数的余数
		int sum = 0, ret = 0;
		for (auto x : nums)
		{
			sum += x; // 算出当前位置的前缀和
			int r = (sum % k + k) % k; // 修正后的余数
			if (hash.count(r)) ret += hash[r]; // 统计结果
			hash[r]++;
		}
		return ret;
	}
};